<html>

<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 
  <link rel="stylesheet" title="Default" href="http://acm.math.spbu.ru/~sk1/colorer/my.css">

  <script src="http://acm.math.spbu.ru/~sk1/colorer/highlight.js"></script>
  <script src="http://acm.math.spbu.ru/~sk1/colorer/cpp.js"></script>
  <script>hljs.initHighlightingOnLoad();</script>
</head>

<body>

<pre><code>
/**
 * Author: Sergey Kopeliovich (Burunduk30@gmail.com)
 * Date: 2012.05.31
 * MaxTest: not more than 0.06 sec on all tests
 * 
 * Description:
 *   Now that we need o(V) time to push flow throw the path.
 *   o(V) = distance from sink to edge with capacity = 0
 */

#include &lt;cassert&gt;
#include &lt;cstdio&gt;
#include &lt;cstdlib&gt;
#include &lt;cstring&gt;
#include &lt;algorithm&gt;
#include &lt;iostream&gt;

using namespace std;

#define forn(i, n) for (int i = 0; i &lt; (int)(n); i++)

typedef long long ll;

const int maxV = 5000;
const int maxE = 60002;
const int maxC = (int)1e9;

int e = 2, n, m, S, T, K;
int head[maxV], next[maxE], fr[maxE], to[maxE], c[maxE], c0[maxE];
int cur[maxV], next2[maxE];
int cc, u[maxV], d[maxV];
int qst, qen, q[maxV];
ll res = 0;

int dfs( int v, int maxF )
{
  if (v == T)
    return maxF;

  int df = 0, &e = cur[v];
  while (df + K &lt;= maxF)
  {
    while (e && c[e] &lt; K)
      e = next2[e];
    if (!e)
      break;
    int add = dfs(to[e], min(maxF - df, c[e]));
    if (add == 0)
      e = next2[e];
    else
      c[e] -= add, c[e ^ 1] += add, df += add;
  }
  return df;
}

int Phase()
{
  cc++;
  qst = qen = 0;
  q[qen++] = S, u[S] = cc, d[S] = 0;
  while (qst &lt; qen)
  {
    int x, v = q[qst++];
    for (int i = head[v]; i; i = next[i])
      if (c[i] &gt;= K && u[x = to[i]] != cc)
      {
        u[x] = cc, d[x] = d[v] + 1;
        q[qen++] = x;
      }
  }
  if (u[T] != cc)
    return 0;

  memset(cur, 0, sizeof(cur));
  forn(v, n)
    for (int i = head[v]; i; i = next[i])
      if (d[to[i]] == d[v] + 1)
        next2[i] = cur[v], cur[v] = i;
  res += dfs(S, maxC);
  return 1;
}

int main()
{
  freopen("flow2.in", "r", stdin);
  freopen("flow2.out", "w", stdout);

  assert(scanf("%d%d", &n, &m) == 2);
  forn(i, m)
  {
    int a, b, _c;
    assert(scanf("%d%d%d", &a, &b, &_c) == 3);
    a--, b--;
    c0[i] = _c;
    next[e] = head[a], to[e] = b, c[e] = _c, head[a] = e++;
    next[e] = head[b], to[e] = a, c[e] = 0, head[b] = e++;
  }

  S = 0, T = n - 1;
  for (K = 1 &lt;&lt; 30; K; K /= 2)
    while (Phase())
      ;

  cout &lt;&lt; res &lt;&lt; endl;
  forn(i, m)
    printf("%d\n", c0[i] - c[2 * i + 2]);
  return 0;
}

</code></pre>

</body>
</html>

<font style="visibility:hidden">
